package com.yiwenup.leetcode.top_interview_150;

import com.yiwenup.leetcode.RandomNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 文件描述
 *
 * @Project struct-algorithm
 * @Package com.yiwenup.leetcode.top_interview_150
 * @Author yiwenup
 * @Date 2024-12-16 20:43:35
 * @Description https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150
 */
public class No0138 {
    public RandomNode copyRandomList(RandomNode head) {
        Map<RandomNode, RandomNode> map = new HashMap<>();
        RandomNode cur = head;
        while (cur != null) {
            map.put(cur, new RandomNode(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
    
    public RandomNode copyRandomList2(RandomNode head) {
        RandomNode dummyHead = new RandomNode(-1);
        RandomNode cur = head;
        RandomNode pre = dummyHead;

        Map<RandomNode, RandomNode> map = new HashMap<>();
        while (cur != null) {
            if (!map.containsKey(cur)) {
                map.put(cur, new RandomNode(cur.val));
            }
            pre.next = map.get(cur);

            if (cur.random != null) {
                if (!map.containsKey(cur.random)) {
                    map.put(cur.random, new RandomNode(cur.random.val));
                }
                pre.next.random = map.get(cur.random);
            }

            cur = cur.next;
            pre = pre.next;
        }

        return dummyHead.next;
    }
    
    public RandomNode copyRandomList3(RandomNode head) {
        RandomNode dummyHead = new RandomNode(-1);
        RandomNode p = head;
        RandomNode q = dummyHead;
        Map<RandomNode, RandomNode> map = new HashMap<>();

        while (p != null) {
            RandomNode copyNode = new RandomNode(p.val);
            map.put(p, copyNode);
            q.next = copyNode;

            p = p.next;
            q = q.next;
        }

        p = head;
        q = dummyHead.next;
        while (p != null) {
            if (p.random != null) {
                q.random = map.get(p.random);
            }

            p = p.next;
            q = q.next;
        }

        return dummyHead.next;
    }
}
